package lq1460;
//lq1460,AC
public class Main {

	public static void main(String[] args) {
		
		//每个节点和1之间的最短路径数，下标从1开始为节点编号
		int[] dp = new int[2021+1];
		
		//2和1的路径长度
		dp[2] = lcm(1,2);
		
		//动态规划思想计算后面每个点v
		//递推到2021
		
		//3至22的情况
		for(int v=3;v<=22;v++) {
			int ans=Integer.MAX_VALUE;
			//遍历当前点和前面的每个点
			for(int u=v-1;u>=2;u--) {
				//v到1的距离
				int a = lcm(1,v);
				//v通过前序点到1的距离
				int b = lcm(u,v)+dp[u];
				//v通过u到1的最小化路径
				int c = Math.min(a, b);
				
				if(ans>c)
					ans = c; 
			}
			dp[v] = ans;
		}
		
		//23到2021的递推，往前递推
		for(int v=23;v<=2021;v++) {
			int ans=Integer.MAX_VALUE;
			//遍历v的21个前序点
			for(int u=v-21;u<v;u++) {
				//找通过前序点到1的最短路径值
				//通过当前前序点到1的路径值
				int a = lcm(u,v)+dp[u];
				if(ans>a)
					ans = a;
			}
			dp[v] = ans;
		}
        System.out.println(dp[2021]) ;
        
        
		
		/*
        //优化代码后的合并写法
        //动态规划
        for (int i =2; i<= 2021; i++) {
            dp[i]= Integer.MAX_VALUE ;
        }
        //当前dp[j] 表示 从 1~j的最短距离
        //dp[j] 可以是 当前 1~j的最短距离 或者 前一状态 到 该点的最短距离
        //当前点往后递推
        for (int i = 1; i<= 2020; i++ )
            for (int j= i+1 ; j<=2021 && (j-i<=21); j++) {
                dp[j] = Math.min(dp[j], dp[i] + lcm(i, j) ) ;
            }  
        System.out.println(dp[2021]) ;
        */ 
	}

	
	//GCD最大公因数
	static int gcd(int a, int b) {
	    return b == 0 ? a : gcd(b, a % b);
	}
	
	//LCM最小公倍数
	static int lcm(int a,int b) {
		return a / gcd(a,b)*b;
	}
}
